#pragma once
#include <assert.h>

#include <vector>
#include <array>
#include <algorithm>

#include <iostream>

template <typename Key, typename Value>
class QueryMapVector
{
public:
    using ArrayIndex = std::vector<int>;
    using ArrayKey = std::vector<Key>;
    using ArrayValue = std::vector<Value>;
    class Iterator
    {
    public:
        std::pair<const Key&, Value &> operator->()
        {
            return **this;
            // return std::make_pair(map_ptr_->keys_[map_ptr_->indexs_[pos_]], map_ptr_->values_[map_ptr_->indexs_[pos_]]);
        }
        std::pair<const Key&, Value &> operator*()
        {
            return std::pair<const Key&, Value &>{map_ptr_->keys_[map_ptr_->indexs_[pos_]], map_ptr_->values_[map_ptr_->indexs_[pos_]]};
            // return std::make_pair(map_ptr_->keys_[map_ptr_->indexs_[pos_]], map_ptr_->values_[map_ptr_->indexs_[pos_]]);
        }
        Iterator &operator--(void)
        {
            assert(0 != pos_);
            if (-1 == pos_) {
                pos_ = int(map_ptr_->size()) - 1;
            }
            else {
                --pos_;
            }
            return *this;
        }
        Iterator &operator++(void)
        {
            assert(-1 < pos_);
            ++pos_;
            if (pos_ == map_ptr_->size()) {
                pos_ = -1;
            }
            return *this;
        }
        bool operator==(const Iterator &o) const
        {
            return (map_ptr_ == o.map_ptr_)
               and (pos_ == o.pos_);
        }
        bool operator!=(const Iterator &o) const
        {
            return !(*this == o);
        }
    private:
        QueryMapVector *map_ptr_;
        int pos_;
        friend QueryMapVector;
    private:
        Iterator() = delete;
        Iterator(const QueryMapVector *map_ptr, int pos)
            : map_ptr_(const_cast<QueryMapVector*>(map_ptr))
            , pos_(pos)
        {}
    };
public:
    QueryMapVector()
        : indexs_{}
        , keys_{}
        , values_{}
        , sorted_{true}
        , size_{0}
        {}
    size_t size() const
    {
        return size_;
    }
    Iterator begin() const
    {
        static Iterator iter(this, 0);
        return iter;
    }
    Iterator end() const
    {
        static Iterator iter(this, -1);
        return iter;
    }
    Iterator find(const Key &key) const
    {
        // assert(sorted_);
        if (0 == size_) return end();
        int l = 0, r = size_ - 1;
        while (l < r) {
            int mid = (l + r) / 2;
            if (keys_[indexs_[mid]] == key) {
                return Iterator(this, mid);
            }
            else if (keys_[indexs_[mid]] < key) {
                l = mid + 1;
            }
            else {
                r = mid - 1;
            }
        }
        return end();
    }
    Value &operator[](const Key &key)
    {
        auto iter = find(key);
        if (end() == iter) {
            iter = push_back(key, Value());
        }
        return values_[indexs_[iter.pos_]];
    }
    std::pair<Iterator, bool> emplace(const Key &key, Value &&value)
    {
        auto iter = find(key);;
        if (end() != iter) {
            return std::make_pair(end(), false);
        }
        return std::make_pair(push_back(key, std::move(value)), true);
    }
    void sort()
    {
        std::sort(indexs_.begin(), indexs_.end(), [this](int i1, int i2){
                return keys_[i1] < keys_[i2];
                });
        sorted_ = true;
        for (int i = 0; i+1 < size_; ++i) {
            if (keys_[i] == keys_[i+1]) {
                std::cerr << "key [" << keys_[i] << "]重复\n";
                assert(false);
            }
        }
    }
private:
    ArrayIndex indexs_;
    ArrayKey keys_;
    ArrayValue values_;
    bool sorted_;
    size_t size_;
private:
    Iterator push_back(const Key &key, Value &&value)
    {
        keys_.push_back(key);
        values_.push_back(std::move(value));
        indexs_.push_back(size_);
        int pos = size_;
        ++size_;
        sorted_ = false;
        std::cout << "push_back\n";
        return Iterator(this, pos);
    }
    // template <typename K, typename V>
    // Iterator push_back(std::pair<const K, V> &pair) {
    //     return push_back(pair.first, std::move(pair.second));
    // }
};
